A local area network (LAN) is a communications network that spans a relatively small area. Most LANs are confined to a single building or group of buildings. However, LANs can be connected to other networks, such as the Internet, using communication channels. LANs can locally connect terminal devices such as workstations, personal computers, printers, entertainment devices, sensors, and telephones. There are many different types of LANs, Ethernet being the most common.
A wireless local area network (WLAN) is a shared-medium communication network that transmits information over wireless channels between terminals within radio transmission range. IEEE 802.11 is a communication standard for WLANs, see O'Hara et al., “IEEE 802.11 Handbook, A Designer's Companion,” IEEE Press, 1999, and “IEEE 802.11 e/D5.0, Draft Supplement to Part 11: Wireless Medium Access Control (MAC) and physical layer (PHY) specifications: Medium Access Control (MAC) Enhancements for Quality of Service (QoS).” The medium access method of (MAC) of IEEE 802.11 is called a distributed coordination function (DCF), which is based on carrier sense multiple access/collision avoidance (CSMA/CA) protocol.
IEEE 802.11 wireless networks can be configured in two different modes: ad hoc and infrastructure modes. In ad hoc mode, all wireless terminals within communication range can communicate directly with each other. The present invention can be applied to Wireless LAN operating both in infrastructure mode and ad hoc mode. The IEEE 802.11a standard specifies eight transmission bit rates at 6, 9, 12, 18, 24, 36, 48, and 54 Mbps, and the 802.11b standard specifies four rate at 1, 2, 5.5, and 11 Mbps. With such a physical-layer enhancement, a terminal can select a best transmission rate depending on a quality of the wireless channel measured by the signal-to-noise ratio (SNR) or packet error rate. When used properly, a multi-rate WLAN greatly improves throughput and effectively supports communication-intensive multimedia applications.
In the context of scheduling a series of packets between terminals, i.e., a ‘packet flow’, the multi-rate WLAN poses new challenges for designing network protocols. Packet scheduling, particularly fair queuing, provides packet-level quality of services (QoS) in terms of throughput and delay, to enable both delay-sensitive and throughput-sensitive applications. Wireless packet scheduling should also address location-dependent channel errors in wireless networks, and shields short-term error bursts from packet flows. Location-dependent errors are a particular concern when terminals are mobile.
However, prior art wireless fair packet scheduling typically assumes a single, fixed transmission rate for all terminals, and does not consider multiple rates for different terminals, where at least one terminal is transmitting at a different rate than all other terminals. As a result, fair queuing methods that are designed for single-rate networks suffer from significant throughput reduction in VvLANs based on the 802.11a/b/g standards. In fact, even the prior art fairness notion may not be justified.
In wireless fair scheduling, packet flows, in the presence of channel errors, seek to approximate a QoS that is equivalent to idealistic, error-free channel conditions. To this end, transmissions of error-prone packet flows are deferred temporarily while error-free flows advance. This substantially improves the effective channel throughput because only flows that perceive error-free channels transmit packets at any given time.
Compared with error-free services, where all flows perceive error-free channels all of the time, error-prone flows may temporally lag behind and error-free flows lead ahead in short periods of time. However, these leading flows delay their future transmissions when the lagging flows perceive error-free channels in order to compensate for the time the lagging flows were deferred.
This way, both leading and lagging flows receive their contracted rates, i.e., throughput, over extended periods of time, and performance bounds in terms of throughput, delay and fairness are preserved over the extended periods of time in the presence of error-prone channels. In prior art design, both models of fair sharing among competing flows and compensation for error-prone flows are defined with respect to throughput. That is, ‘fairness’ means that over an extended period of time, all flows experience a substantial equal throughput.
Roughly speaking, each backlogged flow receives a ‘fair’ share of throughput, defined as ƒ bytes per second. The compensation in the presence of channel errors is also based on throughput.
If an assigned transmission rate of a packet flow ƒ is rƒ, then the flow ƒ receives services during a time period [t, t+ΔT] in proportion to the rate rƒ, as given by
                    S        f            ⁡              (                  t          ,                      t            +                          Δ              ⁢                                                          ⁢              T                                      )              ≈                            r          f                                      ∑                          i              ⁢                                                          ⁢              ε              ⁢                                                          ⁢              B                                ⁢                                          ⁢                      r            i                              ⁢      C      ⁢                          ⁢      Δ      ⁢                          ⁢      T        ,where C is a channel capacity perceived by all flows, B denotes a set of flows that are back-logged due to experiencing an error prone channel, and ΔT is some predetermined time increment.
While such a model is adequate for single-rate WLANS, that model does not work for multi-rate WLANs because the flows have different rates and there is no single channel capacity C. Instead, the channel capacity varies over time depending on the rates assigned to the various terminals. Moreover, normalizing flow throughputs in a multi-rate network leads to significant inefficiencies and mitigates the gains offered by the multi-rate physical layer, because error-prone flows consume a disproportional amount of time and channel resources.
If each terminal in a WLAN can potentially assign different transmission rates at different times, i.e., at least one terminal is transmitting at a different rate than all other terminals, then the fundamental problem is to adapt the compensation models to accommodate such multi-rate options in wireless networks.